import java.util.*;
public class Solution {
    public  static void exchange(int[] input, int a,int b){
        int temp = input[a];
        input[a]= input[b];
        input[b]=temp;
    }
    public  static int partition(int[] input, int start, int end){
        int base = start;
        start = start+1;
        while(start<=end){
            while(start<=end && input[start]<=input[base]){
                start++;
            }
            while(start<=end && input[end]>input[base]){
                end--;
            }
            if(start<end){
                exchange(input,start,end);
            }

        }
        exchange(input,base,start-1);
        return start-1;

    }
    public  static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        return GetLeastNumbers_Solution1(input,0,input.length-1,k);
    }
    public  static ArrayList<Integer> GetLeastNumbers_Solution1(int [] input,int start, int end, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        
        if(k>input.length || k==0){
            return list;
        }
        if(k==input.length){
            for(int i=0; i<input.length; i++){
                list.add(input[i]);
            }
            return list;
        }
        
        int index = partition(input,start,end);
        if(k==index){
            for(int i=0; i<index; i++){
                list.add(input[i]);
            }
            return list;
        }else if(k<index){
            return GetLeastNumbers_Solution1(input, start, index-1,k);
        }else{
            return GetLeastNumbers_Solution1(input, index+1, end,k);
        }
    }



}

